package com.crazyxmq.linear;

import java.util.Iterator;

public class LinkList <T> implements Iterable<T>{

    // 记录头节点
    private Node head;

    // 记录链表长度
    private int N;


    //节点类
    private class Node{
        T item;
        Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }


    public LinkList() {
        //初始化头节点
        this.head = new Node(null,null);
        //初始化个数
        this.N = 0;

    }

    // 清空线性表-单向链表
    public void clear(){
        //把头节点的下一个节点断掉
        head.next = null;

        this.N = 0;
    }

    // 判断线性表是否为空
    public boolean isEmpty(){

        return N == 0;
    }

    // 获取线性表中元素的个数
    public int length(){

        return N;
    }

    // 读取并返回线性表-单向链表的第i个元素的值
    public T get(int i){
        //通过循环，从头开始，找i次
        Node n = head.next;
        for (int index = 0; index < i; index++){
            n = n.next;
        }
        return n.item;
    }

    // 往线性表中插入元素
    public void insert(T t){
        // 找到当前最后一个节点
        Node n = head;
        while (n.next!= null){
            n = n.next;
        }

        // 创建一个新的节点
        Node newNode = new Node(t,null);
        n.next = newNode;
        // 元素个素+1
        N++;

    }

    //[1,2,3,4,5] N=5
    // 0 1 2 3 4
    public void insert(int i ,T t){
        // 找到i位置前的一个节点
        Node pre = head;
        for (int index = 0; index<= i-1;index++){
            pre = pre.next;
        }
        // 找到I 位置的节点
        Node curr = pre.next;

        // 创建一个新的节点
        Node newNode = new Node(t, curr);
        pre.next = newNode;
        N++;
    }

    //[1,2,3,4,5] N=5
    // 0 1 2 3 4
    public T remove (int i){
       // 找到 i 位置的前一个节点
        Node pre = head;
        for (int index = 0; index<= i-1;index++){
            pre = pre.next;
        }
        // 找到i 位置的节点
        Node curr = pre.next;
        // 找到 i 位置后面的一个节点
        Node nextNode= curr.next;
        // 上一个节点指向下一个节点
        pre.next = nextNode;

        // 元素个数 - 1
        N--;

        return curr.item;
    }

    public int indexOf(T t){
       // 从头节点开始，依次找到每一个节点
        Node n = head;
        for (int i = 0;n.next!=null;i++){
            n = n.next;
            if(n.item.equals(t)){
                return i;
            }
        }

        return -1;
    }

    public void resize(int newSize){
        // 定义临时数组
//        T[] temp = eles;
//        // 重新创建一个新数组
//        eles = (T[]) new Object[newSize];
//
//        // 把原有数据再复制过去
//        for (int i =0;i<N;i++){
//            eles[i] = temp[i];
//        }
    }
    @Override
    public Iterator<T> iterator() {
        return new LIterator();
    }



    private class LIterator implements Iterator{

        private Node n;

        public LIterator(){
            this.n = head;
        }

        @Override
        public boolean hasNext() {
            return n.next!= null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }
}
